/*
 * 0047. Majority Element II
 * 给定一个整型数组，找到主元素，它在数组中的出现次数严格大于数组元素个数的三分之一。
 * https://www.lintcode.com/problem/majority-element-ii/description
 * 
 * 样例
 * 给出数组[1,2,1,2,1,3,3] 返回 1
 * 
 * 挑战
 * 要求时间复杂度为O(n)，空间复杂度为O(1)。
 *  
 * 2018.06.23 @jeyming
 */
package majority_element_ii_0047;

import java.util.Collections;
import java.util.List;

public class Majority_element_ii_0047 {
	/*
     * @param nums: a list of integers
     * @return: The majority number that occurs more than 1/3
     */
    public int majorityNumber(List<Integer> nums) {
        // write your code here
        Collections.sort(nums);
		int numsCnt = nums.size() / 3;
		int cnt = 1;
		int tmp = nums.get(0);
		for(int i = 1; i < nums.size(); ++i) {
			if(tmp == nums.get(i)) {
				++cnt;
			} else {
				cnt = 1;
				tmp = nums.get(i);
			}
			if(cnt > numsCnt) {
				return tmp;
			} 
		}
		return 0;
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
